10905. Детская игра

Игрок имеет n положительных чисел. Склеивая их друг с другом, можно получить разные длинные числа. Например, из чисел 123, 124, 56, 90 можно получить 24 разных числа: 1231245690, 1241235690, 5612312490, 9012312456, 9056124123 и так далее. Число 9056124123 является наибольшим среди них.

Для заданного набора чисел следует найти максимальное число, которое можно получить в результате склейки.

Вход. Первая строка каждого теста содержит количество положительных чисел n (n £ 50). Во второй строке следуют сами n чисел. Последний тест содержит n = 0 и не обрабатывается.

Выход. Для каждого теста вывести наибольшее положительное число, которое можно получить в результате склейки чисел.

Пример входа

3

123 127 1239

4

123 124 56 90

5

123 124 56 90 9

5

9 9 9 9 9

0

Пример выхода

9056124123

99056124123

99999

РЕШЕНИЕ

сортировка

Анализ алгоритма

Занесем входные числа в массив строк. Отсортируем строки согласно правилу: строка a меньше строки b тогда и только тогда, когда строка a + b меньше строки b + a (‘+’ – операция конкатенации строк). Строки сортируются по убыванию.

Пример

Рассмотрим первый тест. Последовательность обменов чисел при сортировке имеет вид:

123	127	1239	123127 < 127123
127	123	1239	1231239 < 1239123
127	1239	123	конец

Реализация алгоритма

В символьный массив m будем считывать очередное входное число, преобразовывать в тип string и заносить в s[i]. Все входные числа храним в массиве строк s.

char m[100];

string s[100];

Функция сравнения строк f имеет вид:

int f(string a, string b)

{

return a + b > b + a;

}

Основной цикл программы. Заносим входные слова в строковый массив s.

while(scanf("%d",&n),n)

{

for(i = 0; i < n; i++)

{

scanf("%s",m);

s[i] = string(m);

}

Сортируем строки согласно функции сортировки f.

sort(s,s+n,f);

Последовательно выводим отсортированные строки. Получим наибольшее число, которое можно получить из исходных в результате склейки.

for(i = 0; i < n; i++) printf("%s",s[i].c_str());

printf("\n");

}